package com.jiang.专题.动态规划.Q97;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/02/17 1:35
 */
class Solution {
    // 二维动态规划
    // public boolean isInterleave(String s1, String s2, String s3) {
    //     int n = s1.length(), m = s2.length(), t = s3.length();

    //     if (n + m != t) {
    //         return false;
    //     }

    //     boolean[][] dp = new boolean[n + 1][m + 1];
    //     dp[0][0] = true;

    //     for (int i = 0; i <= n; i++) {
    //         for (int j = 0; j <= m; j++) {
    //             int p = i + j - 1;
    //             if (i > 0) {
    //                 dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
    //             }
    //             if (j > 0) {
    //                 dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
    //             }
    //         }
    //     }
    //     return dp[n][m];
    // }

    // 一维动态规划 + 滚动数组
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[] dp = new boolean[m + 1];
        dp[0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                int p = i + j - 1;
                if (i > 0) {
                    dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(p);
                }
                if (j > 0) {
                    dp[j] = dp[j] || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }
        return dp[m];
    }
}
